import java.util.ArrayList;
import java.util.List;

class Solution1 {
    public List<List<Integer>> res = new ArrayList<>();
    public int[] st;

    public void dfs(int u, int[] nums) {
        if (u == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < u; i++) {
                if (st[i] == 1) {
                    list.add(nums[i]);
                }
            }
            res.add(list);
            return;
        }

        st[u] = 2;
        dfs(u + 1, nums);
        
        st[u] = 1;
        dfs(u + 1, nums);
        st[u] = 0;
    }
    
    public List<List<Integer>> subsets(int[] nums) {
        st = new int[nums.length]; 
        dfs(0, nums);
        return res;
    }
}